#ifndef __BWLIB_NUMBER_THEORY_MODULE_H__
#define __BWLIB_NUMBER_THEORY_MODULE_H__
#include <stdexcept>
#include <algorithm>
#include <limits>
#include "../config.h"
#include "../algorithm/power.cpp"

namespace bwlib
{
	/* @brief: 计算数学意义上的 a mod b
	   @complexity: O(1)
	   @param: a, b
	   @return: a mod b */
	template<typename Type, typename PType>
	inline PType math_mod(
		const Type& a, 
		const PType& b)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(b <= 0) throw std::runtime_error("module a negative number");
#endif
		PType temp = a % b;
		if(temp >= 0)
			return __BWLIB_MOVE(temp);
		return temp + b;
	}

	/* @brief: 计算 a * b mod p
	           对于内置类型，不会产生溢出 
	   @complexity: O(log min(a, b))，decltype(a) == [unsigned] long long
	                O(1)，decltype(a) == [unsigned] int, short, char
	   @param: a, b, p
	   @return: a * b mod p */
	template<typename TA, typename TB, typename TP>
	inline TP mod_mul(const TA& a, const TB& b, const TP& p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		return a * b % p;
	}

	inline unsigned long long mod_mul(
		unsigned long long a, 
		unsigned long long b, 
		unsigned long long p)
	{
		unsigned long long s = 0, t;
		a %= p, b %= p;
		if(a < b) std::swap(a, b);
		while(b)
		{
			if(b & 1)
			{
				t = s;
				s += a;
				if(s >= p || s < t)
					s -= p;
			}

			t = a;
			a <<= 1;
			if(a >= p || a < t)
				a -= p;
			b >>= 1;
		}
		return s;
	}

	inline long long mod_mul(
		long long a, 
		long long b, 
		long long p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		int sign = 0;
		if(a < 0) 
		{
			a = -a;
			sign ^= 1;
		}

		if(b < 0)
		{
			b = -b;
			sign ^= 1;
		}

		if(sign == 0) sign = -1;
		unsigned long long t = mod_mul(
			static_cast<unsigned long long>(a),
			static_cast<unsigned long long>(b),
			static_cast<unsigned long long>(p));
		return -sign * math_mod(static_cast<long long>(t), p);
	}

	inline int mod_mul(int a, int b, int p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		return int((long long)a * b % p);
	}

	inline unsigned mod_mul(unsigned a, unsigned b, unsigned p)
	{
		return unsigned((unsigned long long)a * b % p);
	}

	inline short mod_mul(short a, short b, short p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		return short((int)a * b % p);
	}

	inline unsigned short mod_mul(
		unsigned short a,
		unsigned short b,
		unsigned short p)
	{
		return (unsigned short)((unsigned)a * b % p);
	}

	inline char mod_mul(char a, char b, char p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		return char((int)a * b % p);
	}

	inline unsigned char mod_mul(
		unsigned char a,
		unsigned char b,
		unsigned char p)
	{
		return (unsigned char)((unsigned)a * b % p);
	}

	/* @brief: 计算 a ^ b mod p, 其中 b >= 0
	           对于内置类型，不会产生溢出 
	   @complexity: O(log a * log b)，decltype(a) == [unsigned] long long
	                O(log b)，decltype(a) == [unsigned] int, short, char
	   @param: a, b, p
	   @return: a ^ b mod p */
	template<typename Type>
	inline Type mod_pow(const Type& ta, const Type& tb, const Type& p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(tb < 0) throw std::runtime_error("b < 0 in mod_pow");
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		Type a = ta, b = tb;
		Type t = 1;
		while(b != 0)
		{
			if((b & 1) != 0) 
				t = mod_mul(t, a,  p);
			a = mod_mul(a, a, p);
			b >>= 1;
		}
		return t;
	}

#ifdef __BWLIB_WITH_GMPXX
	template<>
	inline mpz_class mod_pow(
		const mpz_class& a, 
		const mpz_class& b,
		const mpz_class& p)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(b < 0) throw std::runtime_error("b < 0 in mod_pow");
		if(p <= 0) throw std::runtime_error("module a negative number");
#endif
		mpz_class ans;
		mpz_powm(ans.get_mpz_t(), 
			a.get_mpz_t(), 
			b.get_mpz_t(), 
			p.get_mpz_t());
		return ans;
	}
#endif
}

#endif
